package com.atguigu.sort;

import java.util.Arrays;

/**
 * 归并排序，先将元素拆分，然后将元素进行合并
 */
public class MergeSort {

    public static void main(String[] args) {
        int arr[] = {1,4,2,5,3,6,8,7};
        int temp[] = new int[arr.length];
        mergeSort(0,arr.length-1,arr,temp);
        System.out.println(Arrays.toString(arr));

    }

    //分+合方法
    public static void mergeSort(int left,int right,int arr[],int temp[]){
        int mid = (left+right)/2;
        if (left < right){
            mergeSort(left,mid,arr,temp);
            mergeSort(mid+1,right,arr,temp);
            merge(left,right,mid,arr,temp);
        }
    }


    /**
     *
     * @param left 原始数组最左边的元素索引
     * @param right 原始数组最右边元素索引
     * @param mid 中间索引
     * @param arr 原始数组
     * @param temp 临时数组
     */
    public static void merge(int left,int right,int mid,int arr[],int temp[]){
        int i = left;
        int j = mid+1;
        int t = 0;

        //第一步，完成一边元素全部到临时数组
        while (i<=mid && j<=right) {
            if (arr[i] <= arr[j]) {
                temp[t] = arr[i];
                i++;
                t++;
            }else {
                temp[t] = arr[j];
                j++;
                t++;
            }
        }

        //第二步，将剩下元素加入到临时数组
        while (i<=mid){
            temp[t] = arr[i];
            i++;
            t++;
        }

        while (j<=right){
            temp[t] = arr[j];
            j++;
            t++;
        }

        //第三步，把临时数组赋值给原始数组
        int tempLeft = left;
        int k = 0;
        while (tempLeft<=right){
            arr[tempLeft] = temp[k];
            k++;
            tempLeft++;
        }

    }
}
